"""
gpath.py
"""


import random
import time
import yaml
import math
import helper
from simple import SimpleGraph



class GPathError(Exception):
    """Base error class for this module."""
    pass



class ProbabilitiesCheckSumError(GPathError):
    pass



class Individual():
    """Class for representing individuals."""

    def __init__(self, path, start, finish):
        self.genome = []
        self.color  = helper.random_color()
        
        self.path   = path
        self.start  = start
        self.finish = finish
        
        self.score = 0.0


    def create(self, steps):
        """Create a (biased) random individual."""
        pivot = random.choice(self.path.nodes())

        head = self.make_path(steps, pivot, self.start)
        tail = self.make_path(steps, pivot, self.finish)
        head.reverse()

        self.genome = head + [pivot] + tail
    

    def make_path(self, steps, start, goal):
        """Creates a path from start towards goal, not necesarily
        reaching this point."""
        path = []
        
        for step in xrange(steps):

            if start == goal:
                break

            a = helper.str2tuple(start)
            b = helper.str2tuple(goal)
            gradient = helper.make_vector(a, b)
            
            neighbors = self.path.neighbors(start)
            ranking   = self.rank_hood(neighbors, a, gradient)

            next = helper.choice(neighbors, ranking)
            path.append(next)

            start = next

        return path
            

    def rank_hood(self, neighbors, point, gradient):
        """Score the neighbors of a given point by calculating its
        angle to a reference vector."""
        maxi = 2 * math.pi
        rank = []

        for neighbor in neighbors:
            a = helper.str2tuple(neighbor)
            v = helper.make_vector(point, a)

            angle_1 = math.atan2(v.imag, v.real)
            angle_2 = math.atan2(gradient.imag, gradient.real)

            delta = maxi - abs(angle_1 - angle_2)

            rank.append(delta)


        total  = sum(rank)
        divide = lambda x: x / total
        rank   = map(divide, rank)

        return helper.normalize(rank)


    def fitness(self, vector):
        """Evaluate the individual's score."""      
        a = helper.str2tuple(self.genome[0])
        b = helper.str2tuple(self.genome[-1])

        path1 = helper.make_vector(a, b)
        path2 = helper.make_vector(b, a)

        d1 = abs(vector - path1)
        d2 = abs(vector - path2)

        if d1 < d2:
            distance = d1
        else:
            distance = d2

        extra = 0

        if self.genome[0] ==  self.start:
            extra -= 5
        elif self.genome[-1] ==  self.start:
            extra -= 5

        if self.genome[-1] ==  self.finish:
            extra -= 5
        elif self.genome[0] ==  self.finish:
            extra -= 5

        if len(self) < abs(vector):
            extra += 100

        extra += self.has_cycles()

        self.score = (distance * 0.35) + (extra * 0.6) + (len(self) * 0.05)
        return self.score


    def has_cycles(self): 
        path = self.genome
        penalty = 0
        
        for node in path:
            if path.count(node) > 1:
                penalty += 10

        return penalty

        
    def reproduction(self):
        """Performs the reproduction operation."""
        child = Individual(self.path, self.start, self.finish)
        child.genome = self.genome[:]
        
        return child


    def crossover(self, mate):
        """Performs the crossover operation."""
        a = set(self.genome)
        b = set(mate.genome)

        intersection = list(a.intersection(b))

        if intersection:
            # There is, at least, a common point between both paths.
            # Chop up the paths into subpaths from the intersection
            # point, in order to randomly select one posible
            # combination. 

            point = random.choice(intersection)

            slices_a = helper.slice(self.genome, point)
            slices_a[1].reverse()

            slices_b = helper.slice(mate.genome, point)
            slices_b[0].reverse()

            head = random.choice(slices_a)
            tail = random.choice(slices_b)

            new_path = head + [point] + tail

        else:
            edge = (lambda x, y: self.path.has_edge(x, y))
            neighbors = ((x,y) for x in a for y in b if x != y and edge(x,y))

            if neighbors:
                # There are adyacent nodes between the paths. Chop un
                # the paths into subpaths from the adyacent points and
                # then select one posible combination. 

                point_a, point_b = random.choice(neighbors)

                slices_a = helper.slice(self.genome, point_a)
                slices_a[1].reverse()

                slices_b = helper.slice(mate.genome, point_b)
                slices_b[0].reverse()

                head = random.choice(slices_a)
                tail = random.choice(slices_b)

                new_path = head + [point_a, point_b] + tail

            else:
                # There isn't any kind of conection between the
                # paths. Just return one of the paths.

                new_path = random.choice([self.genome, mate.genome])


        child = Individual(self.path, self.start, self.finish)
        child.genome = new_path

        return child

    
    def mutation(self):
        """Performs the mutation operation."""
        point  = random.choice(self.genome)

        slices = helper.slice(self.genome, point)
        slices[1].reverse()

        head = random.choice(slices)
        size = random.randint(0, len(head))
        direction = random.choice([self.start, self.finish])

        child = Individual(self.path, self.start, self.finish)
        child.make_path(len(head), point, direction)
        
        tail = child.genome

        new_path = head + [point] + tail
        child.genome = new_path

        return child
        

    def draw(self):
        name = str(time.time())
        self.path.draw(self.genome, name, self.color)


    def __cmp__(self, other):
        """Comparation between two individuals."""
        return cmp(self.score, other.score)


    def __len__(self):
        return len(self.genome)


    def __repr__(self):
        return str(self.genome) + str(len(self)) + "," + str(self.score) 



class Population():
    """Class for managing populations of individuals."""


    def __init__(self, graph="simple-graph.dot", config="config.yaml"):
        self.graph = SimpleGraph()
        self.graph.read(graph)
        
        self.generation = 0
        self.population = []

        self.operations = ["crossover", "reproduction", "mutation"]
        self.load(config)


    def load(self, config):
        """Reads the configuration file and get all the variables
        ready to use."""

        file = open(config)

        data = yaml.load(file)
        file.close()

        start  = helper.str2tuple(data["start_point"])
        finish = helper.str2tuple(data["finish_point"])
        self.start  = str(start)
        self.finish = str(finish)

        self.vector = helper.make_vector(start, finish)

        self.pop_size = data["pop_size"]
        self.max_size = data["max_size"]
        self.max_generations = data["max_generations"]
        self.tournament_size = data["tournament_size"]
        
        self.probabilities = []
        for operation in self.operations:
            self.probabilities.append(data["probabilities"][operation])

        if not sum(self.probabilities) == 1.0:
            raise ProbabilitiesCheckSumError()


    def create(self):
        """Creates a new random population, overwriting the previous one."""
        self.population = []
        self.generation = 0

        for count in xrange(self.pop_size):
            individual = Individual(self.graph, self.start, self.finish)
            individual.create(self.max_size)
            individual.fitness(self.vector)

            self.population.append(individual)


    def tournament(self, negative=False):
         """Pick up the best (or worst) individual among a pool of individuals."""
         pool = random.sample(self.population, self.tournament_size)

         if negative:
             return max(pool)
         else:
             return min(pool)


    def good_enough(self):
        best  = min(self.population)

        start  = best.genome[0]
        finish = best.genome[-1]

        best.draw()

        forward   = start == self.start and finish == self.finish
        backwards = start == self.finish and finish == self.start

        return forward or backwards


    def evolve(self):
        """Performs the evolution steps"""
        self.create()

        for generation in xrange(self.max_generations):
            
            for replacement in xrange(self.pop_size):
                operation = helper.choice(self.operations, self.probabilities)

                if operation == "crossover":
                    parent1 = self.tournament()
                    parent2 = self.tournament()
                    child   = parent1.crossover(parent2)
                
                elif operation == "reproduction":
                    parent = self.tournament()
                    child  = parent.reproduction()

                elif operation == "mutation":
                    parent = self.tournament()
                    child  = parent.mutation()
                
                child.fitness(self.vector)
                    
                replaced = self.tournament(negative=True)
                self.population.remove(replaced)
                self.population.append(child)


            self.generation += 1
            print self
            
            if self.good_enough(): 
                print "PROBLEM SOLVED"
                return
        

        print "PROBLEM *NOT* SOLVED"


    def draw(self):
        """Draws the graph, higlighting the start and the finish nodes."""
        name = str(time.time())
        self.graph.draw([self.start, self.finish], name, "red")


    def __len__(self):
        return len(self.population)


    def __repr__(self):
        if self.generation != 0:
            best = min(self.population)
            
            avg_fitness = reduce(lambda x,y: x + y.score, self.population, 0.0) 
            avg_fitness /= len(self.population)

            avg_size = reduce(lambda x,y: x + len(y), self.population, 0.0)
            avg_size /= len(self.population)

            message =  ">>> Generation %i\n" % self.generation
            message += ">>> The average size is %f\n" % avg_size
            message += ">>> The average fitness is %f\n" % avg_fitness
            message += ">>> The best fitness is %f\n" % best.score
            message += ">>> The best size is %i\n" % len(best)
            message += ">>> The best individual is %s\n" % best.__repr__()

        else:
            message =  ">>> Generation 0, the process hasn't started yet"

        return message


    
